public class SqrtX {
//    二分查找
//    在不使用sqrt(x) 函数的情况下 得到x平方根的整数部分
    public static void main(String[] args) {
        System.out.println(binarySearch(25));//5
        System.out.println(binarySearch(12));//3
        System.out.println(newton(12));//3
    }
    public static int binarySearch(int x) {
        int index = -1;
        int left = 0;
        int right = x;
        while (left <= right) {
            int mid = left + (right-left)/2;
            if (mid * mid <= x) {
                index = mid;
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return index;
    }


//    牛顿迭代
//    因为x=n*n   x/n=n  可以通过 x/n+n来找到最小值
    public static int newton(int x) {
        if (x == 0) {
            return 0;
        }
        return (int)sqrt2(x,x);
    }
    public static double sqrt2(double n, int x) {
        double res = (x/n + n)/2;
        if (res == n) {
            return n;
        }else {
            return sqrt2(res, x);
        }
    }
}
